Technical Field
The present invention relates to hash functions and, more particularly, to consistent hash functions.
Description of the Related Art
Consider the problem of accessing a distributed number of nodes, called worker, by using a value, called task ID, through an entity, called load balancer (which may include multiple handlers), to perform a task related to the task ID.
An example of this case is where the workers are multiple cache machines with different data cached on them and a client would query a particular text and the cache machine would return a data related to the query. Here, the task is responding to the query and the task ID is the query or more precisely the query text. This is an exemplary query-response scenario.
Another example is when particular procedure needs to be performed by the workers and the result is responded by the worker. For example, consider checking different cryptographic keys on different machines to break an encryption. In this case, the tasks IDs are different cryptographic keys which based on them the task is routed to different workers in the pool by the load balancer. A third example is where the task is not performed in single query and instead a session is established between the client and the worker and subsequent queries with the same task ID would be handled by the same worker.
While the main idea of load balancing across pool of workers is primary, consistency of mapping the task with the same task ID to the same worker (if it exists and the pool of user is stationary and not changing) is usually a secondary requirement for many scenarios. We note that among the three examples mentioned above, the second example does not require the consistency, while the first and third example would require consistency as a secondary condition. The main reason is that there would be a set of data for each query or session that is kept by a particular worker.
Thus, there is a need for consistent hashing.